The number of shortest paths from point A to | vedclass

Name: Exam Paper Generator | JEE NEET Paper Generator | Vedclass
Brand: Vedclass
Rating: 5 (35 reviews)

Question

(B) To find the number of shortest paths from $A$ to $D$,we observe that all paths must pass through the segment $MN$. Let $S_M$ be the set of paths f

Vedclass · Accepted Answer

$186$

Vedclass · Answer

(B) To find the number of shortest paths from $A$ to $D$,we observe that all paths must pass through the segment $MN$. Let $S_M$ be the set of paths from $A$ to $M$ and $S_N$ be the set of paths from $A$ to $N$. Paths from $A$ to $M$: The grid from $A$ to $M$ is $2$ units wide and $5$ units high. The number of paths is $\frac{(2+5)!}{2!5!} = \frac{7!}{2!5!} = 21$. Paths from $M$ to $D$: The grid from $M$ to $D$ is $2$ units wide and $2$ units high. The number of paths is $\frac{(2+2)!}{2!2!} = \frac{4!}{2!2!} = 6$. Total paths through $M$ = $21 	imes 6 = 126$. Paths from $A$ to $N$: The grid from $A$ to $N$ is $2$ units wide and $4$ units high. The number of paths is $\frac{(2+4)!}{2!4!} = \frac{6!}{2!4!} = 15$. Paths from $N$ to $D$: The grid from $N$ to $D$ is $2$ units wide and $3$ units high. The number of paths is $\frac{(2+3)!}{2!3!} = \frac{5!}{2!3!} = 10$. Total paths through $N$ = $15 	imes 10 = 150$. Since the segment $MN$ is a single vertical step,any path passing through $M$ must pass through $N$ (or vice versa depending on direction). However,the grid structure shows $M$ is above $N$. Thus,any path from $A$ to $D$ must pass through the segment $MN$. The number of paths through $MN$ is the number of paths from $A$ to $N$ multiplied by the number of paths from $M$ to $D$. Paths through $MN = (	ext{Paths } A 	o N) 	imes (	ext{Paths } M 	o D) = 15 	imes 6 = 90$. Using the Principle of Inclusion-Exclusion for paths through $M$ or $N$: Total paths = (Paths through $M$) + (Paths through $N$) - (Paths through both $M$ and $N$) Total paths = $126 + 150 - 90 = 186$.

The number of shortest paths from point $A$ to $D$ (as shown in the figure) is:

Similar Questions

How many numbers greater than a million can be formed with the digits $2, 3, 0, 3, 4, 2, 3$?

The total number of integral solutions for the equation $xyz = 24$ is:

$A$ man has $10$ friends. In how many ways can he invite one or more of them to a party?

$A$ committee of $5$ members is to be formed out of $3$ trainees,$4$ professors,and $6$ research associates. In how many different ways can this be done if the committee should have all $4$ professors and $1$ research associate $OR$ all $3$ trainees and $2$ professors?

The number of different $6$-digit numbers that are divisible by $10$,which can be formed using the digits $1, 2, 7, 0, 9, 5$?

Vedclass Test Series

Exam Paper Generator

Online Exam Module